home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / othdbm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  18.8 KB  |  637 lines
  1. /*-----------------------------------------------------------------------------
  2. OTHDBM.C
  3.  
  4. Revision History
  5. ----------------
  6. Jon Ward    17 Oct 1988    Initial Revision.
  7. Jon Ward    30 Oct 1988    Mods for move type.
  8. Jon Ward    30 Oct 1988    Optimized and combined the allocate functions.
  9.                   Now we use the macros ALLOCATE_LIMB and
  10.                   ALLOCATE_BOARD.
  11. Jon Ward    04 Dec 1988    Debugging commencing.
  12. Jon Ward    03 Jan 1989    Added relinking ability to db_delete_subtree
  13.                   changed free_limb from static to global.
  14. -----------------------------------------------------------------------------*/
  15.  
  16. #include <string.h>
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <malloc.h>
  20.  
  21. #include "othello.h"
  22.  
  23.  
  24. /*-----------------------------------------------------------------------------
  25. How This Thing Works:
  26. There will be two data spaces. One for limbs, and one for boards. Each data
  27. space will be maintained as an array. Each array will be bit-mapped so that
  28. we can determine if an element in the array is unused.
  29. -----------------------------------------------------------------------------*/
  30.  
  31. /*------------------------------------------------
  32. The following structure bd_row_st is used as a
  33. trick to get the MSC compiler to perform a struct
  34. assignment for the board row. The reason for this
  35. is that the database boards are stored in a far
  36. area of ram. Segmentation...Argh!!!!
  37.  
  38. The dbm_board_st struct is a compressed form of
  39. the board_st structure used every else in the
  40. program. The boards, when compressed, are much
  41. smaller, about 52% smaller or 66% as big as they
  42. would have been.
  43. ------------------------------------------------*/
  44.  
  45. struct bd_row_st
  46.   {
  47.   unsigned char row [8];
  48.   };
  49.  
  50. struct dbm_board_st
  51.   {
  52.   struct bd_row_st board [8];
  53.   unsigned char fa_bits [FA_BITS_SIZE];
  54.   };
  55.  
  56. typedef struct dbm_board_st dbm_board_type;
  57.  
  58.  
  59. #define MAX_DBM_LIMBS  65536 / sizeof (limb_type)
  60. #define MAX_DBM_BOARDS 32768
  61.  
  62. STATIC limb_type far limb_array [MAX_DBM_LIMBS];
  63.  
  64. STATIC key_type num_limbs_left;        /* number of limbs available */
  65. STATIC key_type num_boards_left;    /* number of boards available */
  66.  
  67. #define MAX_BD_PTRS        50
  68. #define STORED_BOARD_SIZE    sizeof (dbm_board_type)
  69.  
  70. STATIC key_type bd_per_blk = 16384 / STORED_BOARD_SIZE;
  71. STATIC dbm_board_type far *board_ptrs [MAX_BD_PTRS];
  72. STATIC int bd_blks;
  73.  
  74. typedef unsigned int am_type;        /* availability map type */
  75. #define AM_SIZE (8 * sizeof (am_type))    /* bits in availability map type */
  76.  
  77. STATIC am_type lam [(MAX_DBM_LIMBS + 7) / 8];    /* limb availability map */
  78. STATIC am_type bam [(MAX_DBM_BOARDS + 7) / 8];    /* board availability map */
  79.  
  80. #define AM_USED ((am_type) (-1))
  81.  
  82. #define LAM_SIZE (sizeof (lam) / sizeof (lam [0]))
  83. #define BAM_SIZE (sizeof (bam) / sizeof (bam [0]))
  84.  
  85.  
  86. /*-----------------------------------------------
  87. The following macros are used to GET, SET, and
  88. CLR bits in the limb and board availability maps.
  89. -----------------------------------------------*/
  90.  
  91. #define GET_BIT(x,y) (((x) [(y) / AM_SIZE]) &   (1 << ((y) % AM_SIZE)))
  92. #define SET_BIT(x,y) (((x) [(y) / AM_SIZE]) |=  (1 << ((y) % AM_SIZE)))
  93. #define CLR_BIT(x,y) (((x) [(y) / AM_SIZE]) &= ~(1 << ((y) % AM_SIZE)))
  94.  
  95.  
  96. key_type max_limb_key = MAX_DBM_LIMBS;        /* maximum key number for limbs */
  97. key_type max_board_key = MAX_DBM_BOARDS;    /* maximum key number for boards */
  98.  
  99. key_type last_parent_key;    /* last parent child was added to */
  100. key_type last_child_key;    /* last child added */
  101.  
  102.  
  103. /*-----------------------------------------------------------------------------
  104.                          Local Function Prototypes
  105. -----------------------------------------------------------------------------*/
  106. STATIC key_type allocate_limb (int am_sel);
  107. STATIC void free_board (key_type board);
  108. STATIC void free_subtree (key_type key);
  109. STATIC void get_board (
  110.   key_type key,
  111.   board_type *board);
  112. STATIC void put_board (
  113.   key_type key,
  114.   board_type *board);
  115.  
  116.  
  117. /*-----------------------------------------------------------------------------
  118. The following data is used by the allocate_am function when searching for and
  119. allocating a limb or board element in the database.
  120. -----------------------------------------------------------------------------*/
  121.  
  122. struct am_struct
  123.   {
  124.   am_type *am;        /* pointer to availability map */
  125.   key_type size;    /* number of elements in availability map */
  126.   key_type *max;    /* maximum key for am */
  127.   int *num_avail;    /* number of available elements */
  128.   };
  129.  
  130.  
  131. STATIC struct am_struct am_data [] =
  132.   {
  133.     { lam, LAM_SIZE, &max_limb_key,  &num_limbs_left },
  134.     { bam, BAM_SIZE, &max_board_key, &num_boards_left },
  135.   };
  136.  
  137.  
  138. #define ALLOCATE_LIMB()  (allocate_am (0))
  139. #define ALLOCATE_BOARD() (allocate_am (1))
  140.  
  141.  
  142. /*-----------------------------------------------------------------------------
  143. STATIC key_type allocate_am (int am_sel);
  144.  
  145. This function will locate the next available element in either the limb or
  146. board array. The am_sel argument determines whether the limb (0) or board (1)
  147. map will be used. If a free element if found, it is marked as used, and the
  148. key for referencing that element is returned. If no free space is available,
  149. the NO_KEY manifest constant is returned to indicate an allocation failure.
  150. -----------------------------------------------------------------------------*/
  151.  
  152. STATIC key_type allocate_am (int am_sel)    /* availability map selector */
  153. {
  154. struct am_struct *amp;    /* pointer into availability map structure */
  155. register am_type *pt;    /* pointer into the limb availability map */
  156. register key_type key;    /* key var */
  157.  
  158.  
  159. amp = &am_data [am_sel];    /* init pointer to am struct */
  160.  
  161.  
  162. for (pt = amp->am; pt < (amp->am + amp->size); pt++)
  163.   {
  164.   if (*pt != AM_USED)                /* if a limb is free */
  165.     {
  166.     am_type am_entry;                /* var copy of am entry */
  167.  
  168.     key = AM_SIZE * (pt - amp->am);
  169.     am_entry = *pt;
  170.  
  171.     for (; am_entry & 1; am_entry >>= 1, key++);    /* generate the key */
  172.  
  173.     if (key >= *(amp->max))    /* range check the key */
  174.       break;            /* break if it's too big */
  175.  
  176.     SET_BIT (amp->am, key);    /* set alloc bit if range ok */
  177.     *(amp->num_avail) -= 1;    /* decrement number available */
  178.  
  179.     return (key);        /* return the key */
  180.     }
  181.   }
  182.  
  183. return (NO_KEY);                /* out of limb space */
  184. }
  185.  
  186.  
  187. /*-----------------------------------------------------------------------------
  188. void free_limb (key_type limb);
  189.  
  190. This function will free the array element associated with a previously
  191. allocated limb. The limb argument id the index for the array element to free.
  192. The limb is freed merely by clearing the corresponding bit in the limb
  193. availability map.
  194. -----------------------------------------------------------------------------*/
  195.  
  196. void free_limb (key_type limb)
  197. {
  198. if (limb >= 0 && limb < max_limb_key && GET_BIT (lam, limb))
  199.   {
  200.   num_limbs_left++;
  201.   CLR_BIT (lam, limb);
  202.   }
  203. }
  204.  
  205.  
  206. /*-----------------------------------------------------------------------------
  207. STATIC void free_board (key_type board)
  208.  
  209. This function will free the array element associated with a previously
  210. allocated board. The board argument id the index for the array element to free.
  211. The board is freed merely by clearing the corresponding bit in the board
  212. availability map.
  213. -----------------------------------------------------------------------------*/
  214.  
  215. STATIC void free_board (key_type board)
  216. {
  217. if (board >= 0 && board < max_board_key && GET_BIT (bam, board))
  218.   {
  219.   num_boards_left++;
  220.   CLR_BIT (bam, board);
  221.   }
  222. }
  223.  
  224.  
  225.  
  226. /*-----------------------------------------------------------------------------
  227. void db_init (void);
  228.  
  229. This function will clear the othello database manager variables and prepare
  230. some data space for the othello program to use. It should only be called once
  231. to initialize the database.
  232.  
  233. Return Value
  234. None.
  235. -----------------------------------------------------------------------------*/
  236.  
  237. /*-----------------------------------------------
  238. The following pragma declares the memset function
  239. to generate inline code
  240. -----------------------------------------------*/
  241. #pragma intrinsic (memset)
  242.  
  243. void db_init ()
  244. {
  245. key_type blk_size;            /* block size for allocation */
  246. key_type max_boards;
  247.  
  248. memset (lam, 0, LAM_SIZE);    /* clear limb availability map */
  249. memset (bam, 0, BAM_SIZE);    /* clear board availability map */
  250.  
  251. last_parent_key = NO_KEY;
  252. last_child_key = NO_KEY;
  253.  
  254. blk_size = bd_per_blk * STORED_BOARD_SIZE;
  255.  
  256. for (bd_blks = 0; bd_blks < MAX_BD_PTRS; bd_blks++)
  257.   {
  258.   if ((board_ptrs [bd_blks] = _fmalloc (blk_size)) == NULL)
  259.     break;
  260.   }
  261.  
  262. max_boards = bd_blks * bd_per_blk;
  263. if (max_boards < max_board_key)
  264.   max_board_key = max_boards;
  265.  
  266. num_limbs_left = max_limb_key;        /* set maximum limb var */
  267. num_boards_left = max_board_key;    /* set maximum board var */
  268.  
  269.  
  270. #if 0
  271. printf ("Maximum boards = %d\n\n", max_board_key);    /***/
  272. #endif
  273. }
  274.  
  275.  
  276. /*-----------------------------------------------------------------------------
  277. void db_kill (void);
  278.  
  279. This function frees the memory allocated for the database.
  280. -----------------------------------------------------------------------------*/
  281.  
  282. void db_kill (void)
  283. {
  284. register int i;
  285.  
  286. for (i = 0; i < bd_blks; i++)
  287.   _ffree (board_ptrs [i]);
  288. }
  289.  
  290.  
  291. /*-----------------------------------------------------------------------------
  292. key_type db_add_child (key_type parent_key,
  293.             unsigned char move,
  294.             board_type *board,
  295.             int score)
  296.  
  297. This function will add a new child board to the look-ahead move tree. The move
  298. argument contains the move required to get to the board. The score argument
  299. contains the numerical value of the board. The parent_key argument indexes the
  300. parent of the new child.
  301.  
  302. Return Value
  303. The key for the new child leaf, or -1 if there is no more space in the database
  304. for additions.
  305. -----------------------------------------------------------------------------*/
  306.  
  307. key_type db_add_child (key_type parent_key,
  308.             move_type move,
  309.             board_type *board,
  310.             int score)
  311. {
  312. key_type child_key;
  313. limb_type far *limb;
  314.  
  315.  
  316. if ((child_key = ALLOCATE_LIMB ()) == NO_KEY)
  317.   {
  318.   /*** Handle no more limb space condition ***/
  319.   }
  320.  
  321.  
  322. /*-----------------------------------------------
  323. Check to see if the parent's child_key is really
  324. a board key.  If it is, free the board and point
  325. the parent to its first born child.
  326. -----------------------------------------------*/
  327.  
  328. if (parent_key != NO_KEY)
  329.   {
  330.   limb = &limb_array [parent_key];
  331.  
  332.   if (limb->move & BOARD_MASK)
  333.     {
  334.     limb->move &= ~BOARD_MASK;
  335.     free_board (limb->bc.child_key);
  336.     limb->bc.child_key = child_key;
  337.     }
  338.   }
  339.  
  340.  
  341. /*-----------------------------------------------
  342. Save the board, move, score, and sibling for this
  343. limb.
  344. -----------------------------------------------*/
  345.  
  346. limb = &limb_array [child_key];
  347.  
  348. if ((limb->bc.child_key = ALLOCATE_BOARD ()) == NO_KEY)
  349.   {
  350.   free_limb (child_key);
  351.   /*** handle condition of no board space available ***/
  352.   }
  353.  
  354.  
  355. limb->move = move | BOARD_MASK;
  356. limb->score = score;
  357. limb->sibling_key = NO_KEY;
  358.  
  359. put_board (limb->bc.child_key, board);
  360.  
  361.  
  362. /*-----------------------------------------------
  363. If we are adding children other than the first
  364. to a parent, add these children to the end of the
  365. sibling list.
  366.  
  367. Update the new last parent and last child vars.
  368. -----------------------------------------------*/
  369.  
  370. if (parent_key != NO_KEY)
  371.   {
  372.   if (last_parent_key == parent_key)
  373.     {
  374.     limb_array [last_child_key].sibling_key = child_key;
  375.     }
  376.  
  377.   else if (limb_array [parent_key].bc.child_key != child_key)
  378.     {
  379.     key_type temp;
  380.  
  381.     temp = limb_array [parent_key].bc.child_key;
  382.  
  383.     while (limb_array [temp].sibling_key != NO_KEY)    /* find last child */
  384.       temp = limb_array [temp].sibling_key;
  385.  
  386.     limb_array [temp].sibling_key = child_key;
  387.     }
  388.  
  389.   last_parent_key = parent_key;            /* save current parent */
  390.   last_child_key = child_key;            /* save current child */
  391.   }
  392.  
  393. return (child_key);
  394. }
  395.  
  396.  
  397. /*-----------------------------------------------------------------------------
  398. int db_retrieve_board (key_type key,
  399.             board_type *board)
  400.  
  401. This function will retrieve a board from the board database. The key argument
  402. specifies the index for the board to retrieve. The board argument will be
  403. initialized to reflect the board stored in the database.
  404.  
  405. Return Value
  406.      0    board successfully retrieved
  407.     -1    board not allocated, not retrieved
  408. -----------------------------------------------------------------------------*/
  409.  
  410. int db_retrieve_board
  411.   (key_type key,        /* index into board database */
  412.   board_type *board)        /* board to init from database */
  413. {
  414. if (!GET_BIT (bam, key))    /* if the board is not allocated */
  415.   return (-1);            /* return error code */
  416.  
  417. get_board (key, board);        /* get the board */
  418.  
  419. return (0);            /* return success code */
  420. }
  421.  
  422.  
  423. /*-----------------------------------------------------------------------------
  424. limb_type far *db_retrieve_limb (key_type key)
  425.  
  426. This function will retrieve the limb referenced by the key argument. If the key
  427. is out of range, or if the limb is not marked as allocated a NULL pointer
  428. will be returned. If the limb does exist, a far pointer to the limb structure
  429. will be returned.
  430. -----------------------------------------------------------------------------*/
  431.  
  432. limb_type far *db_retrieve_limb (key_type key)
  433. {
  434. if (key >= 0 && key < max_limb_key)
  435.   if (GET_BIT (lam, key))
  436.     return (&limb_array [key]);
  437.  
  438. return (NULL);
  439. }
  440.  
  441.  
  442. /*-----------------------------------------------------------------------------
  443. STATIC void free_subtree (key_type key);
  444.  
  445. This function is called by the db_delete_subtree function and recursively
  446. calls itself to remove all siblings and children starting with the child
  447. referenced by the key argument.
  448. -----------------------------------------------------------------------------*/
  449.  
  450. STATIC void free_subtree (register key_type key)
  451. {
  452. limb_type far *pt;        /* pointer to the limb */
  453. static key_type sibling;    /* copy of the sibling index */
  454.  
  455. do
  456.   {
  457.   pt = &limb_array [key];
  458.   ((pt->move & BOARD_MASK) ? free_board : free_subtree) (pt->bc.child_key);
  459.   sibling = pt->sibling_key;
  460.   free_limb (key);
  461.   key = sibling;
  462.   }
  463. while (key != NO_KEY);
  464. }
  465.  
  466.  
  467. /*-----------------------------------------------------------------------------
  468. int db_delete_subtree (
  469.    key_type parent,
  470.    key_type child)
  471.  
  472. This function will delete the sub-tree referenced by the index stored in the
  473. child argument. If no limb exists at child, nothing will be deleted.
  474. -----------------------------------------------------------------------------*/
  475.  
  476. int db_delete_subtree (
  477.    key_type parent,
  478.    register key_type child)
  479. {
  480. limb_type far *ch_pt;        /* pointer to the child limb */
  481. limb_type far *l;        /* pointer to child in chain */
  482. key_type far *left_link;    /* link of previous sibling or parent */
  483. key_type chk;            /* current child of parent */
  484.  
  485.  
  486. last_parent_key = NO_KEY;
  487. last_child_key = NO_KEY;
  488.  
  489.  
  490. /*------------------------------------------------
  491. Attempt to get a pointer to the child and parent
  492. limbs.  If either is NULL, return indicating an
  493. error.
  494. ------------------------------------------------*/
  495.  
  496. if ((ch_pt = db_retrieve_limb (child)) == NULL)
  497.   return (-1);
  498.  
  499. if ((l = db_retrieve_limb (parent)) == NULL)
  500.   return (-1);
  501.  
  502.  
  503. /*------------------------------------------------
  504. Loop thru the children of the parent searching for
  505. the specified child.  If found, link either the
  506. parent or the previous sibling to the following
  507. sibling.  If no mathing child was found, return
  508. an error.
  509. ------------------------------------------------*/
  510.  
  511. chk = *(left_link = &(l->bc.child_key));
  512. for (; chk != NO_KEY; chk = l->sibling_key)
  513.   {
  514.   l = db_retrieve_limb (chk);
  515.  
  516.   if (chk == child)
  517.     {
  518.     *left_link = l->sibling_key;
  519.     break;
  520.     }
  521.  
  522.   left_link = &(l->sibling_key);
  523.   }
  524.  
  525. if (chk != child)
  526.   return (-1);
  527.  
  528.  
  529. /*------------------------------------------------
  530. Now, delete the child and his subtree.
  531. ------------------------------------------------*/
  532.  
  533. ((ch_pt->move & BOARD_MASK) ? free_board : free_subtree) (ch_pt->bc.child_key);
  534. free_limb (child);
  535.  
  536. return (0);
  537. }
  538.  
  539.  
  540. /*-----------------------------------------------------------------------------
  541. int db_almost_full (void);
  542.  
  543. This function returns a value of 1 if there are less than 40 boards or limbs
  544. remainaing unmapped in the database. A value of 0 is returned if there are at
  545. least 40 limbs AND boards unmapped.
  546. -----------------------------------------------------------------------------*/
  547.  
  548. int db_almost_full (void)
  549. {
  550. return (num_limbs_left < 40 || num_boards_left < 40) ? 1 : 0;
  551. }
  552.  
  553.  
  554. /*-----------------------------------------------------------------------------
  555. void init_borders (board_type *bd);
  556.  
  557. Fill the board boarders with the proper values.
  558. -----------------------------------------------------------------------------*/
  559.  
  560. void init_borders (board_type *bd)
  561. {
  562. register unsigned char *p;
  563. register unsigned char *end;
  564.  
  565. memset (bd->board [0], OFF_BOARD | BD_AX | FD_AX | H_AX | V_AX, 10);
  566. memset (bd->board [9], OFF_BOARD | BD_AX | FD_AX | H_AX | V_AX, 10);
  567.  
  568. end = bd->board [9];
  569. for (p = bd->board [1]; p < end; p+=10)
  570.   {
  571.   p [0] = OFF_BOARD | BD_AX | FD_AX | H_AX | V_AX;
  572.   p [9] = OFF_BOARD | BD_AX | FD_AX | H_AX | V_AX;
  573.   }
  574. }
  575.  
  576.  
  577. /*-----------------------------------------------------------------------------
  578. STATIC void get_board (
  579.   key_type key,
  580.   board_type *board);
  581.  
  582. This function gets the board whose key is key from the database and stores the
  583. board data in the structure pointed to by the board argument.
  584. -----------------------------------------------------------------------------*/
  585.  
  586. STATIC void get_board (
  587.   key_type key,
  588.   board_type *board)
  589. {
  590. div_t ndx;
  591. dbm_board_type far *dbm_bd;
  592. register int i;
  593.  
  594. ndx = div (key, bd_per_blk);
  595. dbm_bd = &(board_ptrs [ndx.quot]) [ndx.rem];
  596.  
  597. for (i=0; i<8; i++)
  598.   *((struct bd_row_st *) &(board->board [i+1][1])) = dbm_bd->board [i];
  599.  
  600. for (i=0; i<FA_BITS_SIZE; i++)
  601.   board->fa_bits [i] = dbm_bd->fa_bits [i];
  602.  
  603. init_borders (board);
  604. }
  605.  
  606. /*-----------------------------------------------------------------------------
  607. STATIC void put_board (
  608.   key_type key,
  609.   board_type *board);
  610.  
  611. This function stores the board pointed to by the board argument into the
  612. database at the location indicated by the key argument.
  613. -----------------------------------------------------------------------------*/
  614.  
  615. STATIC void put_board (
  616.   key_type key,
  617.   board_type *board)
  618. {
  619. div_t ndx;
  620. dbm_board_type far *dbm_bd;
  621. register int i;
  622.  
  623. ndx = div (key, bd_per_blk);
  624. dbm_bd = &(board_ptrs [ndx.quot]) [ndx.rem];
  625.  
  626. for (i=0; i<8; i++)
  627.   dbm_bd->board [i] = *((struct bd_row_st *) &(board->board [i+1][1]));
  628.  
  629. for (i=0; i<FA_BITS_SIZE; i++)
  630.   dbm_bd->fa_bits [i] = board->fa_bits [i];
  631. }
  632.  
  633.  
  634. /*-----------------------------------------------------------------------------
  635. -----------------------------------------------------------------------------*/
  636.  
  637.